package BinarySearch.Medium;

public class LC0034 {
    public int[] searchRange(int[] nums, int target) {
        int N = nums.length;
        if (N < 1) return new int[]{-1, -1};

        double minorTarget = target - 0.5, majorTarget = target + 0.5;
        // 利用二分搜索确定元素插入位置的特性，寻找target的左右边界
        int left = 0, right = N, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] > minorTarget) right = mid;
            else left = mid + 1;
        }
        int minorTargetIdx = left;

        left = 0;
        right = N;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] > majorTarget) right = mid;
            else left = mid + 1;
        }
        int majorTargetIdx = left;
        if (minorTargetIdx >= majorTargetIdx) return new int[]{-1, -1};
        else return new int[]{minorTargetIdx, majorTargetIdx - 1};
    }

    /**
     * 用一种“更二分”（每次舍弃一半元素）的方法来解决此问题。详细解释参考Markdown文件。
     */
    public int[] searchRangeMoreBS(int[] nums, int target) {
        int N = nums.length;
        if (N < 1 || nums[0] > target || nums[N - 1] < target) return new int[]{-1, -1};

        int leftBound, rightBound;

        // 寻找左边界
        int left = 0, right = N - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        } // 退出时有left==right
        leftBound = left;
        if (nums[leftBound] != target) return new int[]{-1, -1}; // target不存在

        // 寻找右边界
        left = 0;
        right = N - 1;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] <= target) {
                if (left < mid) left = mid;
                else break; // 此时应有left+1==right
            }
            else right = mid - 1;
        }
        rightBound = nums[right] <= target ? right : left;

        return new int[]{leftBound, rightBound};
    }
}
